package com.love.labuladong.stack;

import java.util.Arrays;
import java.util.Stack;

/**
 * @Author : zh
 * @Description :
 *
 * 输入一个数组nums，请你返回一个等长的结果数组，结果数组中对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。函数签名如下：
 *
 * int[] nextGreaterElement(int[] nums);
 *
 *比如说，输入一个数组nums = [2,1,2,4,3]，你返回数组[4,2,4,-1,-1]。因为第一个 2 后面比 2 大的数是 4;
 *  1 后面比 1 大的数是 2；
 *  第二个 2 后面比 2 大的数是 4;
 *  4 后面没有比 4 大的数，填 -1；
 *  3 后面没有比 3 大的数，填 -1。
 *
 * @Date : 2024-08-13 09:10
 */
public class MonotoneStack {


    public static void main(String[] args) {
        int[] nums = {2,1,2,4,3};
        int[] ints = nextGreaterElement(nums);

        System.out.println(Arrays.toString(ints));
    }

    /**
     * 方法一
     * @param nums
     * @return
     */
   static int[] nextGreaterElement(int[] nums){
        if(nums == null || nums.length == 0){
            return nums;
        }
        int n = nums.length;
        int[] res = new int[n];
        // 大底栈
        Stack<Integer> stack = new Stack<>();

        //1. 倒着往栈里面放元素
        for (int i = n - 1; i >= 0; i--){
            // 2. 栈里面留的是严格大于左边的元素 （所以栈里和原数组相同的数也把他弹出来）
            while (!stack.isEmpty() && nums[i] >= stack.peek() ){
                stack.pop();
            }
            // 3.
            res[i] = stack.isEmpty() ? -1 : stack.peek();
            // 4.
            // 2,3,4 的顺序很重要
            stack.push(nums[i]);
        }
        return res;
    }



    // 流程 ： 栈根据题意是大底栈 或 是小底栈 （严格顺序）[放下标]
    // 关键! 不同题目中相等值出现时的处理！用后续的题目说明



}
